package jiaoheng;

import org.junit.Test;

/**
 * 名称
 * 思路
 * 代码（主要卡点，关键点）
 * 最优复杂度
 * 最差复杂度
 * 平均复杂度
 * 查找次数
 * 交换次数
 * 稳定性(大小相同的两个值排序前后顺序是否总不变)
 */
public class 排序 {
    /**
     * 冒泡排序
     *    就跟狗熊掰棒子一样，遇见大的就交换手里的棒子，比冒泡排序更形象，因为有"狗熊"这个概念，代表的是承载着最大值的下标，最终每次都把最大值选出来放到最后就完成了
     *    这里的概念有：数组，数组长度，当前的狗熊位置（每次狗熊出现的位置都是数据组的第一个位置0），需要的狗熊数(或者狗熊需要跑几趟)才能把数组的数排好序
     *    概念之间的关系（并不需要每个概念都有一个变量，不然变量之间都是有关系的，有一个变动，其他都要变动，维护起来就会很麻烦，容易出bug）
     *    所以，首先是知道需要狗熊跑几趟？假如数组长度是arr.length，则需要arr.length-1趟，循环表示就是 for(int i=1;i<=arr.length-1;i++)，或者for(int i=1;i<arr.length -1 ;i++)
     *    每一趟他需要走几步，第一趟需要走 arr.length-1，最后一趟是1步，中间的步数是arr.length-1 - 已经搬到对的位置上的元素数量(i-1)
     * 依次把最大的值移动到最后面。从第一个值开始，依次和后面的值进行比较，如果第一个值大于后面一个值，则交换两者的位置，否则不交换，最终是要把最大值交换到数组后面
     * 这里的i代表的是循环次数，是数组长度arr.length）
     */
    @Test
    public void bubboSort(){
        int[] arr = {2,4,1,5,3};
        for(int i=0;i<arr.length -1 ;i++){ // 需要多少只狗熊，和下表结合在一起
            for(int j=0;j<arr.length -1-i;j++){ // 让需要走的步数隐藏在下标里，用下标表示
                if(arr[j]>arr[j+1]){
                    int tmp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=tmp;
                }
            }
        }
        for(int i=0;i<arr.length ;i++){
            System.out.println(arr[i]);
        }
    }

    /**
     * 选择排序
     * 可以先想象成额外一个数组，然后选择最小值往里放（其实为了省空间，利用的当前数组）
     * 记下最小值位置
     */
    @Test
    public void selectSort(){
        int[] arr = {2,4,1,5,3};
        for(int i=0;i<arr.length-1;i++){
            int selectIndex = i;
            for(int j=selectIndex;j<arr.length-1;j++){
                if(arr[j+1]<arr[selectIndex]){ //关键点是arr[selectIndex]和arr[j+1]比较
                    selectIndex = j+1;
                }
            }
            if(i!=selectIndex){
                int tmp=arr[i];
                arr[i]=arr[selectIndex];
                arr[selectIndex]=tmp;
            }
        }
        for(int i=0;i<arr.length ;i++){
            System.out.println(arr[i]);
        }
    }

    /**
     * 这里想象成两个数组，比较好写代码，不过空间使用的同一个
     * 写的麻烦是因为一个写变量时，经常一个数字有很多含义，得考虑影响
     *
     * 排好序的数组位置
     * 未排好序的数组位置
     * 从未排好序的数组中选出的数，在排好序的数组中排序时的定位
     */
    @Test
    public void insertSort(){
        int[] arr = {2,4,1,5,3};
        for(int i=1;i<arr.length;i++){ // 要插入的数据,所以使用1，如果定义了变量，最后也会取消掉，太冗余
            int insertDataIndex = i; //感觉不加入它下面没法冒牌了
            for(int j=i-1;j>=0;j--){// j代表的是排好序的数组的下表，从大到小排
                if(arr[j]>arr[insertDataIndex]){
                    int tmp=arr[j];
                    arr[j]=arr[insertDataIndex];
                    arr[insertDataIndex]=tmp;
                    insertDataIndex--;
                }else{
                    break;
                }
            }
        }
        for(int i=0;i<arr.length ;i++){
            System.out.println(arr[i]);
        }
    }

    /**
     * 希尔排序
     * 假设，希尔排序，把最小的数切换到了前面，又能省下多少次交换？
     */
    @Test
    public void shellSort(){
        int[] arr = {2,4,1,5,3};
        // 初始增量设置为数组长度一半
        for(int gap=arr.length/2;gap>0;gap/=2){
            // 从每个子序列的第gap个元素开始，逐步进行插入排序
            for(int i=gap;i<arr.length;i++){ //这里是分成的每个组,从后面的分组开始++
                int insertData= arr[i]; // 这里取出值，相当于给插入的队列留下空位
                int j;
                for(j=i;j>=gap;j-=gap){
                    if(arr[j-gap]<insertData){
                        arr[j]=arr[j-gap];
                    }
                }
                arr[j] = insertData;
            }
        }
        for(int i=0;i<arr.length ;i++){
            System.out.println(arr[i]);
        }

    }
    /**
     * 冒泡排序
     * 从数组第一个元素开始，以此跟数组中后面的数字进行比较
     * 如果前面的数字比后面的数字大，则交换位置，否则不做任何操作
     * 最终数组中最后一个数字就是最大的数字
     * 就像水里的气泡一样，最大的数字会放到最后
     * 依次循环完成后，数组中的数字就是有序的了
     */
    /**
     * 写代码时，先写内层循环，再写外层循环
     * 外层循环要从
     */
    @Test
    public void 冒泡排序简化(){
        int[] arr = {3, 5, 1, 2, 4};
        // 这里多循环几次也不会有问题，不影响下标
        for(int j=0;j<arr.length-1;j++){
            // 这里主要为了防止越界，优化的话就是再减去j
            for(int i=0;i<arr.length-1;i++){
                if(arr[i] > arr[i+1]){
                    int tmp=arr[i];
                    arr[i]=arr[i+1];
                    arr[i+1]=tmp;
                }
            }
        }
        for(int number : arr){
            System.out.println(number);
        }
    }
    public void 冒泡排序优化(){
        int[] arr = {3, 5, 1, 2, 4};
        // 这里的次数是arr.length-1次，从0开始计数，所以这里要j<arr.length-2
        // 这里多循环几次也没大问题
        for(int j=0;j<arr.length-2;j++){
            // 这里循环的结束条件很重要，这里要循环arr.length-1次，因为从0开始算第一次，所以这里写<，可以保证其不会越界
            // 这里的-j，是为了让每次循环都少一次，因为每次循环都会把最大的数字放到最后面，所以每次循环都要少一次(不减也不会出错，更像冒泡，但确实不好)
            // for循环i是可以取到小于的那个数的
            for(int i=0;i<arr.length-1-j;i++){
                if(arr[i] > arr[i+1]){
                    int tmp=arr[i];
                    arr[i]=arr[i+1];
                    arr[i+1]=tmp;
                }
            }
        }
        for(int number : arr){
            System.out.println(number);
        }
    }

    // 简化的选择排序（但实际课本上交的都是稍微有点优化的版本）
    // 就是把第一个值和后面的值进行比较，如果第一个值比后面的值大，则交换位置，否则不做任何操作
    // 优化版本的就是在内层循环中，每次循环都记录最小值的下标，然后交换位置，这样每次循环都少一次，时间复杂度O(n2)，减少交换次数



    /**
     * @Author jiaoheng
     * 时间复杂度总是O(n2)
     * 空间复杂度O(1)
     * 稳定
     *
     * 算法重点是，把排序数组分为排好序的和未排好序的两组，
     * 每次循环未排好序数组，选取最小的值排在已排好序数组的最后面
     *
     * 内层循环的起始位置是i+1，内存循环上有最小值标识；选择的时候临时保存的是未排好序部分最小值的下标
     *
     * 选择排序不稳定，比如 110，排序后011，两个1的位置可能就交换了
     * @Date 2021/6/23 8:18
     **/
    @Test
    public void 选择排序(){
        int[] arr = {3, 5, 1, 2, 4};
        for(int i=0;i<arr.length-1;i++){//循环次数
            int minPosition = i;
            for(int j=i+1;j<arr.length;j++){//循环位置
                if(arr[minPosition] > arr[j]){
                    minPosition = j;//记录本次循环最小值的位置
                }
            }
            int minValue = arr[minPosition];
            arr[minPosition] = arr[i];
            arr[i] = minValue;
        }
        //输出
        for (int index:arr) {
            System.out.print(index+",");
        }
    }

    /**
     *  插入排序在数据基本有序的情况下执行更好
     *  灵感来自于扑克牌的插入，每次从未排序的队列中选择一个，然后插入到已排序队列中
     *  插入排序，开始想成比较已排好序的队列时从0开始排...
     * 当不知道循环多少次，
     *
     * 时间复杂度：最优 O(n)，平均和最坏 O(n²)
     * 空间复杂度：O(1) 原地排序
     *
     **/
    @Test
    public void 插入排序(){
        int[] arr = {3, 5, 1, 2, 4};
        // 遍历从第二个元素开始的所有元素（i表示当前待插入位置）
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];  // 当前需要插入的元素
            int j = i - 1;     // 从已排序序列的末尾开始比较

            // 将比key大的元素依次后移
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }

            // 插入元素到正确位置
            arr[j + 1] = key;
        }
        //输出
        for (int index:arr) {
            System.out.print(index+",");
        }
    }

    @Test
    public void mergeSortTest(){
        int[] arr = {3, 5, 1, 2, 4};
        mergeSort(arr,0,arr.length-1);
        for(int i=0;i<arr.length;i++){
            System.out.println(arr[i]);
        }
    }
    // 拆分的时候,left和right代表要处理数组的开始和结束下标
    // 一直递归拆分到只剩下一个值
    public void mergeSort(int[] arr,int left,int right){
        if(left<right){
            int mid = left + (right-left)/2;
            // 递归对左半部分进行排序
            mergeSort(arr,left,mid);
            // 递归对右半部分进行排序
            mergeSort(arr,mid+1,right);
            // 合并两个数组
            merge(arr,left,mid,right);
        }
    }
    // 合并的时候需要middle，分割两个要合并的数组
    // 合并到一个新数组中
    // 合并两个子数组的函数
    public static void merge(int[] array, int left, int mid, int right) {
        // 计算左右子数组的长度
        int n1 = mid - left + 1; // 左子数组长度
        int n2 = right - mid;    // 右子数组长度

        // 创建临时数组
        int[] leftArray = new int[n1];
        int[] rightArray = new int[n2];

        // 将数据复制到临时数组中
        for (int i = 0; i < n1; i++) {
            leftArray[i] = array[left + i];
        }
        for (int j = 0; j < n2; j++) {
            rightArray[j] = array[mid + 1 + j];
        }

        // 合并临时数组回原数组
        int i = 0, j = 0, k = left; // 初始化索引
        while (i < n1 && j < n2) {
            if (leftArray[i] <= rightArray[j]) {
                array[k] = leftArray[i];
                i++;
            } else {
                array[k] = rightArray[j];
                j++;
            }
            k++;
        }

        // 复制剩余的元素（如果有）
        while (i < n1) {
            array[k] = leftArray[i];
            i++;
            k++;
        }
        while (j < n2) {
            array[k] = rightArray[j];
            j++;
            k++;
        }
    }

    @Test
    public void quickSortTest(){
        int[] arr = {3, 5, 1, 2, 4};
        quickSort(arr,0,arr.length-1);
        for(int i=0;i<arr.length;i++){
            System.out.println(arr[i]);
        }
    }
    public void quickSort(int[] arr,int left,int right){
        if(left < right){
            int selectPosition = partition(arr,left,right);
            //selectPosition 位置上的元素已经处于最终的排序位置，不需要再参与后续的排序操作,所以直接-1
            // 对左半部分递归排序
            quickSort(arr,left,selectPosition-1);
            // 对右半部分递归排序
            quickSort(arr,selectPosition+1,right);
        }
    }
    // 返回选择值的位置
    public int partition(int[] arr,int left,int right){
        // 选取最后位置的值做分割值
        int selectValue = arr[right];
        int i = left -1; //代表小于基准值的右边界，这个值很重要，初始化为要处理数组的左边界-1
        for(int j=left;j<right;j++){
            if(arr[j]<=selectValue){
                i++;
                int tmp=arr[j];
                arr[j]=arr[i];
                arr[i]=tmp;
            }
        }
        int tmp = arr[i+1];
        arr[i+1]=arr[right];
        arr[right]=tmp;
        return i+1;
    }

}
